package com.atwulidun.rbtree;

import java.util.Scanner;

public class RBTreeDemo {
    public static void main(String[] args) {
        // 新增结点
//        insertOpt();
        // 删除结点
        deleteOpt();
    }

    public static void insertOpt() {
        Scanner scanner = new Scanner(System.in);
        RBTree<String, Object> rbt = new RBTree<>();
        while (true) {
            System.out.println("请输入你要插入的结点：");
            String key = scanner.next();
            System.out.println();
            rbt.put(key.length() == 1 ? ("0" + key) : key, null);
            TreeOperation.show(rbt.getRoot());
        }
    }

    public static void deleteOpt() {
        RBTree<String, Object> rbt = new RBTree<>();
        //预先造10个节点（1-10）
        for (int i = 1; i < 11; i++) {
            rbt.put((i + "").length() == 1 ? "0" + i : i + "", null);
        }
        TreeOperation.show(rbt.getRoot());
        //以下开始删除
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("请输入你要删除的节点:");
            String key = scanner.next();
            System.out.println();
            rbt.remove(key.length() == 1 ? "0" + key : key);
            TreeOperation.show(rbt.getRoot());
        }
    }
}

class RBTree<K extends Comparable<K>, V> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private RBNode root;

    public RBNode getRoot() {
        return root;
    }

    // put方法
    public void put(K key, V value) {
        // 一、如果key为null，则抛出空指针异常
        if (key == null) {
            throw new NullPointerException();
        }

        // 二、如果root为null，则新建一个RBNode赋给root
        if (root == null) {
            // 如果value为null，则将value处的值变成key的值即可
            root = new RBNode<>(null, key, value = value == null ? (V) key : value);
            return;
        }

        // 三、寻找插入的位置
        RBNode parent = null;// 定义一个父结点
        RBNode temp = root;// 定义一个临时结点
        int cmp = 0;// 存放比较结果
        while (temp != null) {
            // 将当前临时结点作为父结点
            // 注意这里的巧妙之处：当temp == null进不了while循环时，parent刚好就是叶子结点！！！！！！！！！！！！！！！！！！！！！
            parent = temp;
            // 获取插入的key值和当前父结点的key值的比较结果
            cmp = key.compareTo((K) parent.key);
            // 如果插入的key值比父结点的值小，则继续往父结点左边找
            if (cmp < 0) {
                temp = temp.left;
            } else if (cmp > 0) {
                // 如果插入的key值比父结点的值大，则继续往父结点右边找
                temp = temp.right;
            } else {
                // 如果key值相等，则只需要把父结点的value值覆盖掉即可(若value为null，则用key值覆盖)
                parent.value = value == null ? (V) key : value;
                // 特别注意：覆盖之后直接return即可！！！！！！！！！！！！！！！！！！
                return;
            }
        }

        // 四、根据找到的插入位置，创建新结点，同时需要判断要插入的位置是当前父结点的左边还是右边，插入新结点
        // 创建新结点
        RBNode<K, Object> kObjectRBNode = new RBNode<>(parent, key, value = value == null ? (V) key : value);
        // 挂在父结点左边
        if (cmp < 0) {
            parent.left = kObjectRBNode;
        } else {
            // 挂在父结点右边
            parent.right = kObjectRBNode;
        }
        // 五、对新增的结点进行调整
        fixAfterPut(kObjectRBNode);
    }

    // 增加结点后对红黑树进行调整的方法
    // 分为六种情况：
    // 三结点转换为四结点时(情况一、二需要进行一次旋转；情况三、四需要进行两次旋转。调整过后最顶上结点一定是黑色的！！！！！！！！)
    // 情况一(左倾)：父结点是爷爷结点的左结点，叔叔结点为null，当前结点是父结点的左结点；
    // 情况二(左倾)：父结点是爷爷结点的左结点，叔叔结点为null，当前结点是父结点的右结点；
    // 情况三(右倾)：父结点是爷爷结点的右结点，叔叔结点为null，当前结点是父结点的左结点；
    // 情况四(右倾)：父结点是爷爷结点的右结点，叔叔结点为null，当前结点是父结点的右结点；
    // 四结点裂变时(不需要旋转，调整之后最顶上结点是红色的，需要对当前结点的爷爷结点再一次进行调整！！！！！！！！！！！)
    // 情况五(左倾)：父结点是爷爷结点的左结点，叔叔结点不为null；
    // 情况六(右倾)：父结点是爷爷结点的右结点，叔叔结点不为null
    private void fixAfterPut(RBNode x) {
        // 新增进来结点为红色
        x.color = RED;
        // 只有父结点为红色才需要调整，避免双红出现
        // x == root是为了让四结点裂变时能跳出循环；x.parent.color == BLACK是为了让三结点转换为四结点时能跳出循环！！！！！！！！
        while (x != null && x != root && x.parent.color == RED) {
            // 1.若x的父结点是爷爷结点的左孩子
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                // 获取叔叔结点，根据叔叔结点是否存在又可以再分为两种情况(三结点转换为四结点时，四结点裂变时)
                RBNode uncle = rightOf(parentOf(parentOf(x)));
                // (1)四结点裂变时，叔叔结点存在，不需要旋转
                if (colorOf(uncle) == RED) {
                    // 把父结点变黑
                    setColor(parentOf(x), BLACK);
                    // 把叔叔结点变黑
                    setColor(uncle, BLACK);
                    // 把爷爷结点变红
                    setColor(parentOf(parentOf(x)), RED);
                    // 注意：此时爷爷结点的父结点可能为红色，需要把当前结点的引用赋给爷爷结点再一次进行调整!!!!!!!!!!!!
                    x = parentOf(parentOf(x));
                } else {
                    // (2)三结点转换为四结点时，叔叔结点不存在
                    // 先进行第一次的旋转
                    // 如果当前结点是父结点的右孩子，则将当前结点的引用x指向左结点，再对x左旋
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        leftRotate(x);
                    }
                    // 把父结点变黑
                    setColor(parentOf(x), BLACK);
                    // 把爷爷结点变红
                    setColor(parentOf(parentOf(x)), RED);
                    // 将爷爷结点右旋转，旋转后最顶上结点一定是黑色，不需要对其再进行调整，此时x.parent.color == BLACK，跳出while循环！！！！！！！
                    rightRotate(parentOf(parentOf(x)));
                }
            } else {
                // 2.若x的父结点是爷爷结点的右孩子
                // 获取叔叔结点
                RBNode uncle = leftOf(parentOf(parentOf(x)));
                // (1)如果存在叔叔结点
                if (colorOf(uncle) == RED) {
                    // 把父结点设置为黑色
                    setColor(parentOf(x), BLACK);
                    // 把叔叔结点设置为黑色
                    setColor(uncle, BLACK);
                    // 把爷爷结点设置为红色
                    setColor(parentOf(parentOf(x)), RED);
                    // 注意：此时爷爷结点的父结点可能为红色，需要把当前结点的引用赋给爷爷结点再一次进行调整!!!!!!!!!!!!
                    x = parentOf(parentOf(x));
                } else {
                    // (2)如果不存在叔叔结点
                    // 先进行第一次的旋转
                    // 如果当前结点是父结点的左孩子，则将当前结点的引用指向父结点，再对x右旋
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rightRotate(x);
                    }
                    // 把父结点设置为黑色
                    setColor(parentOf(x), BLACK);
                    // 把爷爷结点设置为红色
                    setColor(parentOf(parentOf(x)), RED);
                    // 将爷爷结点左旋转，旋转后最顶上结点一定是黑色，不需要对其再进行调整
                    leftRotate(parentOf(parentOf(x)));
                }
            }
        }
        // 如果是因为x = parentOf(parentOf(x));使得x == root而跳出了while循环，此时x的颜色是红色，需要将其设置为黑色
        if (x == root) {
            x.color = BLACK;
        }
        // 也可以写成
//        root.color = BLACK;
    }

    // remove方法对下面的delete方法进行一个封装
    public V remove(K key) {
        RBNode node = getNode(key);
        if (node == null) {
            return null;
        }
        V oldValue = (V) node.value;
        deleteNode(node);
        return oldValue;
    }

    // 根据key查找结点的方法
    private RBNode getNode(K key) {
        // 从根结点开始查找
        RBNode temp = root;
        int cmp = 0;
        while (temp != null) {
            cmp = key.compareTo((K) temp.key);
            // 如果key值小于当前结点的key值，则继续往左找
            if (cmp < 0) {
                temp = temp.left;
            } else if (cmp > 0) {
                // 如果key值大于当前结点的key值，则继续往右找
                temp = temp.right;
            } else {
                // 如果key值等于当前结点的key值，则返回当前结点
                return temp;
            }
        }
        // 特别注意：如果最后没有找到，则返回null
        return null;
    }

    // 删除结点的方法
    // 这里是已经找到具体结点了，再将其删除！！！！！！！！！！
    // 特别容易漏掉认父亲，删除后调整，删除后调整！！！！！！！！！！！
    private void deleteNode(RBNode node) {
        // 3.如果被删除的结点有左右两个子结点
        if (node.left != null && node.right != null) {
            // 找前驱结点作为替代结点
//            RBNode rep = predecessor(node);
            // 找后继结点作为替代结点
            RBNode rep = successor(node);
            // 将被删除结点的key和value都换为替代结点的值
            node.key = rep.key;
            node.value = rep.value;
            // 再将node指向替代结点
            node = rep;
            // 注意这里的小技巧：如果被删除的结点有左右两个子结点，那么经过处理后变成删除只有一个子结点或者没有子结点的情况
            // 如果被删除的结点只有一个子结点或者没有子结点，那么就不走这里if判断的代码，而直接走下面的代码
        }
        // 获取替代结点
        RBNode replacement = node.left != null ? node.left : node.right;
        // replacement可能为node.left，node.right或者null三种情况
        // 2.被删除结点只有一个子结点的情况
        if (replacement != null) {
            // 孩子先认父亲！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
            replacement.parent = node.parent;
            // 父亲再认孩子
            // 此时要判断node是否为根结点
            // 若node为根结点
            if (node.parent == null) {
                root = replacement;
            } else {
                // 若node不为根结点，还需要判断被删除结点是其父结点的左孩子还是右孩子
                // 若被删除结点是其父结点的左孩子
                if (node.parent.left == node) {
                    node.parent.left = replacement;
                } else {
                    // 若被删除结点是其父结点的右孩子
                    node.parent.right = replacement;
                }
            }
            // 让node被垃圾回收
            node.left = node.right = node.parent = null;
            // 对replacement进行调整！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
            if (node.color == BLACK) {
                fixAfterRemove(replacement);
            }
        } else {
            // 1.被删除结点没有子结点的情况
            // 此时要判断node是否为根结点
            // 若node为根结点
            if (node.parent == null) {
                root = null;
            } else {
                // 若node不为根结点，则要先对其进行调整，再分情况删除
                if (node.color == BLACK) {
                    fixAfterRemove(node);
                }
                // 若被删除结点是其父结点的左结点
                if (node.parent.left == node) {
                    node.parent.left = null;
                } else {
                    // 若被删除结点是其父结点的右结点
                    node.parent.right = null;
                }
                // 让node被垃圾回收(因为node为叶子结点，其左右结点都为null，只需要将其父结点置null即可)
                node.parent = null;
            }
        }
    }

    // 删除结点后调整的方法
    private void fixAfterRemove(RBNode x) {
        // 能进入while循环，说明删除的是非根结点的黑色叶子结点！！！！！！！！！
        while (x != root && colorOf(x) == BLACK) {
            // x是左孩子的情况
            if (x == leftOf(parentOf(x))) {
                // 找到其兄弟结点
                RBNode rnode = rightOf(parentOf(x));

                // 判断此时兄弟结点是否是真正的兄弟结点
                // 若兄弟结点是黑色，则是真正的兄弟结点；若是红色则不是真正的兄弟结点，需要进行调整
                // 注：真正的兄弟结点：在2-3-4树中是兄弟结点中的元素，并且在红黑树中也是兄弟结点，即在同一层
                // 非真正兄弟结点：在2-3-4树中是兄弟结点中的元素，但在红黑树中不是兄弟结点，即不在同一层
                if (colorOf(rnode) == RED) {
                    setColor(rnode, BLACK);
                    setColor(parentOf(x), RED);
                    leftRotate(parentOf(x));
                    // 找到真正的兄弟结点，调整后的兄弟结点一定是黑色的
                    rnode = rightOf(parentOf(x));
                }
                // 情况三，找兄弟借，兄弟没得借，则兄弟结点自损
                // 注意：这里颜色为黑指的是空结点！！！！！！！！！！！
                if (colorOf(leftOf(rnode)) == BLACK && colorOf(rightOf(rnode)) == BLACK) {
                    // 兄弟结点自损，颜色由黑变红
                    setColor(rnode, RED);
                    // 如果父结点是红色，那么直接跳出循环，将父结点由黑变红即可弥补父结点所在子树的黑色结点
                    // 如果父结点是黑色，那么只能一层层网上找，直到能从某一个父结点的兄弟结点中找到可借的补偿结点，此时跳出循环；
                    // 如果网上找一直都是黑色结点，那就找到根结点时跳出
                    x = parentOf(x);
                }
                //情况二，找兄弟借，兄弟有的借
                else {
                    // 分2种小情况：兄弟结点本来是3结点或者是4结点的情况
                    // 下面if判断条件是对兄弟结点的右结点进行判断，如果颜色为黑，说明其右结点为空，这是一个三结点
                    // 此时需要将父结点，兄弟结点以及兄弟结点的左结点调整到一条直线上，也就是右倾的情况
                    if (colorOf(rightOf(rnode)) == BLACK) {
                        setColor(leftOf(rnode), BLACK);
                        setColor(rnode, RED);
                        rightRotate(rnode);
                        rnode = rightOf(parentOf(x));
                    }
                    // 下面的代码是对调整过后的三结点以及四结点进行同样的操作
                    setColor(rnode, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(rnode), BLACK);
                    leftRotate(parentOf(x));
                    // 调整好后跳出while循环，以下这句话为跳出循环的条件
                    x = root;
                }
            }
            // x是右孩子的情况
            else {
                // 兄弟节点
                RBNode rnode = leftOf(parentOf(x));
                // 判断此时兄弟节点是否是真正的兄弟节点
                if (colorOf(rnode) == RED) {
                    setColor(rnode, BLACK);
                    setColor(parentOf(x), RED);
                    rightRotate(parentOf(x));
                    //找到真正的兄弟节点
                    rnode = leftOf(parentOf(x));
                }
                // 情况三，找兄弟借，兄弟没得借
                if (colorOf(rightOf(rnode)) == BLACK && colorOf(leftOf(rnode)) == BLACK) {
                    //情况复杂，暂时不写
                    setColor(rnode, RED);
                    x = parentOf(x);
                }
                // 情况二，找兄弟借，兄弟有的借
                else {
                    // 分2种小情况：兄弟结点本来是3结点或者是4结点的情况
                    if (colorOf(leftOf(rnode)) == BLACK) {
                        setColor(rightOf(rnode), BLACK);
                        setColor(rnode, RED);
                        leftRotate(rnode);
                        rnode = leftOf(parentOf(x));
                    }
                    setColor(rnode, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(rnode), BLACK);
                    rightRotate(parentOf(x));
                    x = root;
                }
            }
        }
        // 情况一、替代结点是红色，则直接染红，补偿删除的黑色结点，这样红黑树依然保持平衡
        // 这里对应两种情形：第一种是有一棵子树的结点删除后对其替代结点进行的调整，其替代结点肯定是红色，只需要将其变黑即可
        // 第二种是删除黑色叶子结点向上递归，直到找到一个红色结点，不满足循环的条件colorOf(x) == BLACK而跳出循环，将该红色结点置黑，补偿删掉的黑色结点，
        // 那么红黑树便能保持黑色平衡
        setColor(x, BLACK);
    }

    // 查找某个结点前驱结点的方法
    private RBNode predecessor(RBNode node) {
        if (node == null) {
            return null;
        } else if (node.left != null) {
            RBNode temp = node.left;
            while (temp.right != null) {
                temp = temp.right;
            }
            return temp;
        } else {
            // 如果左子树为空，则一直往上找到第一个左拐处的第一个结点即为前驱结点
            // 譬如找下面③的前驱结点
            //          ②
            //        /    \
            //       ①     ⑤
            //             /
            //            ④
            //           /
            //          ③
            RBNode parent = node.parent;
            RBNode temp = node;
            // 只要temp是parent的左孩子，那就一直往上找，直到temp是parent的右孩子，也就是到达第一个左拐弯处才跳出循环
            while (parent != null && parent.left == temp) {
                temp = parent;
                parent = temp.parent;
            }
            return parent;
        }
    }

    // 查找某个结点后继结点的方法
    private RBNode successor(RBNode node) {
        if (node == null) {
            return null;
        } else if (node.right != null) {
            RBNode temp = node.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            return temp;
        } else {
            // 如果右子树为空，则一直往上找到第一个右拐弯的第一个结点即为后继结点
            // 譬如找下面③的后继结点
            //          ④
            //        /    \
            //       ①     ⑤
            //        \
            //         ②
            //          \
            //           ③
            RBNode parent = node.parent;
            RBNode temp = node;
            // 只要temp是parent的右孩子，那就一直往上找，直到temp是parent的左孩子，也就是到达第一个右拐弯处才跳出循环
            while (parent != null && parent.right == temp) {
                temp = parent;
                parent = temp.parent;
            }
            return parent;
        }
    }

    // 设置结点颜色的方法
    private void setColor(RBNode node, boolean color) {
        if (node != null) {
            node.color = color;
        }
    }

    // 获取结点颜色的方法
    private boolean colorOf(RBNode node) {
        return node == null ? BLACK : node.color;// 注意：空结点的颜色为黑色
    }

    // 获取结点父结点的方法
    private RBNode parentOf(RBNode node) {
        return node == null ? null : node.parent;
    }

    // 获取结点左子结点的方法
    private RBNode leftOf(RBNode node) {
        return node == null ? null : node.left;
    }

    // 获取结点右子结点的方法
    private RBNode rightOf(RBNode node) {
        return node == null ? null : node.right;
    }


    // 左旋的方法

    /**
     * @param p 为旋转点
     *          pf                pf
     *          /                 /
     *          p                 pr(r)
     *          / \               / \
     *          pl  pr(r)  ->     p    rr
     *          / \           / \
     *          rl rr        pl   rl
     */
    private void leftRotate(RBNode p) {
        if (p != null) {
            // 首先要把p的右结点保存下来
            RBNode r = p.right;
            // 一、p和rl确认父子关系
            // 1.p认rl作儿子
            p.right = r.left;
            // 2.rl认p作父亲
            if (r.left != null) {
                r.left.parent = p;
            }
            // 二、r和pf确认父子关系
            // 1.r认pf作父亲
            r.parent = p.parent;
            // 2.pf认r作儿子，分为三种情况
            // (1)如果p为根结点，则其父结点为null，那么要把旋转后的r作为根结点
            if (p.parent == null) {
                root = r;
            } else if (p.parent.left == p) {
                // (2)如果原先p是其父结点的左子结点
                r.parent.left = r;
            } else {
                // (3)如果原先p是其父结点的右子结点
                r.parent.right = r;
            }
            // 三、r和p重新确认父子关系
            // 1.r认p作儿子
            r.left = p;
            // 2.p认r作父亲
            p.parent = r;
        }
    }
    // 右旋的方法

    /**
     * @param p 为旋转点
     *          pf                pf
     *          \                 \
     *          p                 pl(l)
     *          / \               / \
     *          (l)pl  pr  ->       rl   p
     *          / \                    / \
     *          rl rr                  rr  pr
     */
    private void rightRotate(RBNode p) {
        if (p != null) {
            RBNode l = p.left;
            p.left = l.right;
            if (l.right != null) {
                l.right.parent = p;
            }
            l.parent = p.parent;
            if (p.parent == null) {
                root = l;
            } else if (p.parent.left == p) {
                l.parent.left = l;
            } else {
                l.parent.right = l;
            }
            l.right = p;
            p.parent = l;
        }
    }


    static class RBNode<K extends Comparable<K>, V> {
        private RBNode parent;
        private RBNode left;
        private RBNode right;
        private boolean color;
        private K key;
        private V value;

        public RBNode() {
        }

        // 在put方法中用到
        public RBNode(RBNode parent, K key, V value) {
            // 如果新增的第一个结点是根结点，则其应该是黑色的，因为添加完根结点后就return了，没有用到fixAfterPut方法，所以这里应该把RBNode的默认颜色设置为黑色
            this.color = BLACK;
            this.parent = parent;
            this.key = key;
            this.value = value;
        }

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }
}

class TreeOperation {
    /*
    树的结构示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */

    // 用于获得树的层数
    public static int getTreeDepth(RBTree.RBNode root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
    }


    private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) return;
        // 0、默认无色
//       res[rowIndex][columnIndex] = String.valueOf(currNode.getValue());
        //1、颜色表示
        if (currNode.isColor()) {//黑色，加色后错位比较明显
            res[rowIndex][columnIndex] = ("\033[30;3m" + currNode.getValue() + "\033[0m");
        } else {
            res[rowIndex][columnIndex] = ("\033[31;3m" + currNode.getValue() + "\033[0m");
        }
        //2、R,B表示
//        res[rowIndex][columnIndex] = String.valueOf(currNode.getValue()+"-"+(currNode.isColor()?"B":"R")+"");

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;
        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.getLeft() != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.getRight() != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }


    public static void show(RBTree.RBNode root) {
        if (root == null) System.out.println("EMPTY!");
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i++) {
            for (int j = 0; j < arrayWidth; j++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth / 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line : res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}